﻿
namespace Leetcode.N0398;
public class Solution
{

    private (int val, int index)[] nums;
    private Random r;
    public Solution(int[] nums)
    {
        this.nums = new (int val, int index)[nums.Length];

        for (int i = 0; i < nums.Length; i++)
        {
            this.nums[i] = (nums[i], i);
        }
        this.nums = this.nums.OrderBy(i => i.val).ToArray();
        this.r = new Random();
    }

    public int Pick(int target)
    {
        var i = this.Find(target);
        int count = 0;
        var pickIndex = 0;
        for (; i < this.nums.Length && this.nums[i].val == target; i++)
        {
            count++;
            if (this.r.Next(0, count) == 0)
            {
                pickIndex = i;
            }
        }
        return this.nums[pickIndex].index;
    }

    private int Find(int target)
    {
        int from = 0;
        int to = nums.Length - 1;

        while (from <= to)
        {
            var m = from + (to - from) / 2;
            if (this.nums[m].val < target)
            {
                from = m + 1;
            }
            else
            {
                to = m - 1;
            }
        }
        return from;
    }
}